home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / oper_sys / deltablu / list.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-08-17  |  3.7 KB  |  171 lines
  1. /***************************************************************************
  2.  List.c
  3.  
  4.     Implementation of List.h.
  5.     Invariants and relationships:
  6.     slots != NULL
  7.     slotCount > 0
  8.     sizeof(*slots) == slotCount * sizeof(Element)
  9.     0 <= first < slotCount
  10.     -1 <= last < slotCount
  11.     last >= first (if not empty)
  12.     last == first - 1 (if empty)
  13.     NumberOfItems == (last - first) + 1
  14.  
  15. ****************************************************************************/
  16.  
  17. #include <stdio.h>
  18. #include <stdlib.h>
  19. #include "List.h"
  20.  
  21. /* Private Prototypes */
  22. void Error(char*);
  23. void Grow(List);
  24. void MakeRoom(List);
  25.  
  26. /****** Create and Destruction ******/
  27.  
  28. List List_Create(initialCount)
  29. int initialCount;
  30. {
  31.     register List newList;
  32.  
  33.     newList = (List) malloc(sizeof(ListStruct));
  34.     if (newList == NULL) Error("out of memory");
  35.     newList->slots = (Element *) malloc(initialCount * sizeof(Element));
  36.     if (newList->slots == NULL) Error("out of memory");
  37.     newList->slotCount = initialCount;
  38.     newList->first = 0;
  39.     newList->last = -1;
  40.     return newList;
  41. }
  42.  
  43. void List_Destroy(list)
  44. register List list;
  45. {
  46.     if (list->slots == NULL) Error("bad ListStruct; already freed?");
  47.     free(list->slots);
  48.     list->slots = NULL;
  49.     list->slotCount = 0;
  50.     list->first = 0;
  51.     list->last = -1;
  52.     free(list);
  53. }
  54.  
  55. /****** Enumeration and Queries ******/
  56.  
  57. void List_Do(list, proc)
  58. List list;
  59. register Proc proc;
  60. {
  61.     register Element *nextPtr = &(list->slots[list->first]);
  62.     register Element *lastPtr = &(list->slots[list->last]);
  63.  
  64.     while (nextPtr <= lastPtr) {
  65.     (*proc)(*nextPtr++);
  66.     }
  67. }
  68.  
  69. int List_Size(list)
  70. register List list;
  71. {
  72.     return (list->last - list->first) + 1;
  73. }
  74.  
  75. /****** Adding ******/
  76.  
  77. void List_Add(list, element)
  78. register List list;
  79. Element element;
  80. {
  81.     if (list->last >= (list->slotCount - 1)) MakeRoom(list);
  82.     list->slots[++list->last] = element;
  83. }
  84.  
  85. void List_Append(list1, list2)
  86. register List list1;
  87. List list2;
  88. {
  89.     register Element *nextPtr = &(list2->slots[list2->first]);
  90.     register Element *lastPtr = &(list2->slots[list2->last]);
  91.  
  92.     while (nextPtr <= lastPtr) {
  93.     List_Add(list1, *nextPtr++);
  94.     }
  95. }
  96.  
  97. /****** Removing ******/
  98.  
  99. void List_Remove(list, element)
  100. List list;
  101. Element element;
  102. {
  103.     register Element *srcPtr = &list->slots[list->first];
  104.     register Element *destPtr = &list->slots[0];
  105.     register Element *lastPtr = &list->slots[list->last];
  106.     
  107.     list->last = list->last - list->first;
  108.     list->first = 0;
  109.     while (srcPtr <= lastPtr) {
  110.     if (*srcPtr == element) {
  111.         list->last--;
  112.     } else {
  113.         *destPtr++ = *srcPtr;
  114.     }
  115.     srcPtr++;
  116.     }
  117. }
  118.  
  119. Element List_RemoveFirst(list)
  120. register List list;
  121. {
  122.     register Element element;
  123.  
  124.     if (list->last < list->first) return NULL;
  125.     element = list->slots[list->first++];
  126.     return element;
  127. }
  128.  
  129. void List_RemoveAll(list)
  130. register List list;
  131. {
  132.     list->first = 0;
  133.     list->last = -1;
  134. }
  135.  
  136. /****** Private ******/
  137.  
  138. #define max(x, y) ((x) > (y) ? (x) : (y))
  139. #define min(x, y) ((x) < (y) ? (x) : (y))
  140.  
  141. static void Error(errorString)
  142. char* errorString;
  143. {
  144.     printf("List.c error: %s.\n", errorString);
  145.     exit(-1);
  146. }
  147.  
  148. static void Grow(list)
  149. register List list;
  150. {
  151.     list->slotCount += min(max(list->slotCount, 2), 512);
  152.     list->slots = (Element *) realloc(list->slots, (list->slotCount * sizeof(Element)));
  153.     if (list->slots == NULL) Error("out of memory");
  154. }
  155.  
  156. static void MakeRoom(list)
  157. List list;
  158. {
  159.     register Element *srcPtr = &list->slots[list->first];
  160.     register Element *destPtr = &list->slots[0];
  161.     register Element *lastPtr = &list->slots[list->last];
  162.  
  163.     if (((list->last - list->first) + 1) >= list->slotCount) Grow(list);
  164.     if (list->first == 0) return;
  165.     while (srcPtr <= lastPtr) {
  166.     *destPtr++ = *srcPtr++;
  167.     }
  168.     list->last = list->last - list->first;
  169.     list->first = 0;
  170. }
  171.